/*
题目: N皇后Ⅱ
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

https://leetcode.cn/problems/n-queens-ii
 */
public class SolveNQueensⅡ {
    int src = 0;

    public int totalNQueens(int n) {
        boolean[][] board = new boolean[n][n];
        backTrack(board, 0, n);
        return src;
    }

    private void backTrack(boolean[][] board, int pos, int n) {
        if (pos == n) {
            src ++;
            return ;
        }

        // 每一层递归就是对棋盘的一层进行枚举
        for (int j = 0; j < n; j++) {
            board[pos][j] = true;
            if (isValid(board, pos, j, n)) {
                backTrack(board, pos + 1, n);
            }
            board[pos][j] = false;
        }
    }

    private boolean isValid(boolean[][] board, int row, int col, int n) {
        // 检查同一列
        for (int i = 0; i < n; i ++) {
            if (i == row) {
                continue;
            }
            if (board[i][col]) {
                return false;
            }
        }

        // 检查同一行
        for (int i = 0; i < n; i++) {
            if (i == col) {
                continue;
            }
            if (board[row][i]) {
                return false;
            }
        }

        // 检查斜线
        int x = row - 1;
        int y = col + 1;
        while (x >= 0 && y < n) {
            if (board[x][y]) {
                return false;
            }
            x --;
            y ++;
        }

        x = row + 1;
        y = col + 1;
        while (x < n && y < n) {
            if (board[x][y]) {
                return false;
            }
            x ++;
            y ++;
        }

        x = row - 1;
        y = col - 1;
        while (x >= 0 && y >= 0) {
            if (board[x][y]) {
                return false;
            }
            x --;
            y --;
        }

        x = row + 1;
        y = col - 1;
        while (x < n && y >= 0) {
            if (board[x][y]) {
                return false;
            }
            x ++;
            y --;
        }

        return true;
    }
}
